package algorithm.sort;

import java.util.Arrays;

/**
 * @program JavaBase
 * @description: 快速排序
 * @author: zhanglu
 * @create: 2020-06-27 23:43:00
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] sb_arr = new int[]{4,4,6,5,3,2,8,1};
        Sb.quickSort(sb_arr, 0, sb_arr.length - 1);
        System.out.println(Arrays.toString(sb_arr));

        int[] db_arr = new int[]{4,4,6,5,3,2,8,1};
        Sb.quickSort(db_arr, 0, db_arr.length - 1);
        System.out.println(Arrays.toString(db_arr));
    }




}

//双边循环法
class Sb{
    public static void quickSort(int[] arr, int startIndex, int endIndex){
        if(startIndex >= endIndex){
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, endIndex - 1);
        quickSort(arr, startIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
        //取第一个位置(也可以选择随机位置)的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            //控制right指针比较并左移
            while (left < right && arr[right] > pivot){
                right --;
            }
            //控制left指针比较并右移
            while (left < right && arr[left] <= pivot){
                left ++;
            }
            //交换left和right指针所指向的元素
            if(left < right){
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;
            }
        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }
}
//单边循环法
class Db{
    public static void quickSort(int[] arr, int startIndex, int endIndex){
        if(startIndex >= endIndex){
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, endIndex - 1);
        quickSort(arr, startIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] < pivot){
                mark ++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark]= pivot;
        return mark;
    }
}
